package caculate;

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @program: rocsun
 * @description:
 * @author: yx.guo
 * @create: 2025-02-21 23:24
 **/
public class KMPNextArray {

    public static int[] buildNext(String P) {
        int[] next = new int[P.length()];
        int j = 0; // 当前匹配的长度
        // 从第2个字符开始
        for (int i = 1; i < P.length(); i++) {
            // 如果当前字符不匹配，回退到前一个匹配位置
            while (j > 0 && P.charAt(i) != P.charAt(j)) {
                j = next[j - 1];
            }
            // 如果匹配，j向前移动
            if (P.charAt(i) == P.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    /**
     * 构建next数组，用来表示当前点最大前后缀长度
     * @param str
     * @return
     */
    public static int[] buildNext_1(String str) {
        int len  = str.length();
        int[] next = new int[len];

        // 想同时：j表示当前最大前后缀长度；不同时：从j位置开始往前退
        int j = 0;
        for (int i = 1; i < len; i++) {
            // 如果不一样，回退到上个j的位置
            while (j > 0 && str.charAt(j) != str.charAt(i)) {
                /**
                 * 这里之所以使用这种写法
                 *  如果当前值相等，那么next[i] = j+1
                 *  如果不相等，那么需要找上一个匹配长度的字串本身
                 *      如果不存在，那么直接j=0
                 *      如果存在，
                 *          判断是不是为0？
                 *              如果next[j-1]为0，表示该子串不存在公共子串，j=0
                 *              如果next[j-1]不为0，表示该位置存在公共字串（也就是说后面部分也存在公共字串），所以可以直接从next[j-1]位置开始比较
                 *
                 *
                 * 总结：该位置作用其实等同于通过next[]数组，可以用来判断最小不用重复判断的长度，因为该长度的
                 */
                j = next[j - 1];
            }
            // 如果一样，j++
            if (str.charAt(j) == str.charAt(i)) {
                j++;
            }
            next[i] = j;
        }

        return next;
    }

    /**
     * 查询字符串pattern在str中出现的位置
     * @param str
     * @param pattern
     * @return
     */
    public static int KMPsearch(String str, String pattern) {
        if (str.isEmpty()) return -1;
        int[] next = buildNext_1(pattern);

        int j = 0;
        for (int i = 0; i < str.length(); i++) {
            //  根据next回退操纵
            while (j>0 && str.charAt(i) != pattern.charAt(j)) {
                j = next[j-1];
            }
            // 如果相等 j后移，本次循环后i也后移
            if (str.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            // 出口，如果j移到最后一位表示包含该字符串，位置在i-j+1
            if (j == pattern.length()) {
                return i-j+1;
            }
        }
        return -1;
    }

    /**
     * sunday算法查询字符串
     * @param str
     * @param pattern
     * @return
     */
    public static int SundaySearch(String str, String pattern) {
        if (str.isEmpty() || pattern.isEmpty() || pattern.length() > str.length()) return -1;
        int sLen = str.length();
        int pLen = pattern.length();

        // 构造一个偏移表
        Map<Character, Integer> offsetMap = new LinkedHashMap<>();
        for (int i = 0; i < pLen; i++) {
            // 保存最后出现的位置，那么如果使用的话，真正偏移量为 plen - offsetMap.get(pattern.charAt(i))
            offsetMap.put(pattern.charAt(i), pLen - i);
        }

        int i = 0;
        while (i + pLen <= sLen) {
            int j = 0;
            while (j < pLen && str.charAt(i +j) == pattern.charAt(j)) {
                j++;
            }

            if (j == pLen) {
                return i;
            }

            /**
             * 这里需要之所以这么做，是为了避免不必要的移动；
             * 如果目标窗口的下一位在格式串中存在，只需要其与格式串中《最后一个出现的位置》对应起来即可；
             *      这里为什么是最后一个出现的位置呢，如果不是最后一个出现的位置，可能出现跨度过大而漏掉一些必要的匹配；
             * 如果不存在，表示当前目标窗口的下一位不再格式串中，也就是说在匹配时只要包含它就一定不匹配，直接跳过即可；
             *
             */
//            if (i + pLen < sLen)
//                i += offsetMap.getOrDefault(str.charAt(i + pLen), pLen + 1);
            int nextIndex = i + pLen;
            if (nextIndex > sLen - 1) break;
            i += offsetMap.getOrDefault(str.charAt(nextIndex), pLen + 1);
        }

        return -1;
    }

    /**
     * 查找子字符串的暴力算法
     * @param str
     * @param pattern
     * @return
     */
    public static int bruteForceSearch(String str, String pattern) {
        if (str.isEmpty() || pattern.isEmpty() || pattern.length() > str.length()) return -1;
        int slen = str.length();
        int plen = pattern.length();

        for (int i = 0; i <= slen - plen ;) {
            int j;
            for (j = 0; j < plen;j++) {
                if (str.charAt(i+j) != pattern.charAt(j)){
                    break;
                }
            }

            if (j == plen) {
                return i;
            }

            // 暴力算法，这里只需要移动1
            i++;
        }

        return -1;
    }

    public static int sundaySearch_test(String str, String pattern) {
        if (str.isEmpty() || pattern.isEmpty() || pattern.length() > str.length()) return -1;
        int sLen = str.length();
        int pLen = pattern.length();

        int[] next = new int[pLen];
        int j = 0;
        for(int i=1;i<pLen;i++){
            while(j>0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j-1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;;
            }
            next[i] = j;
        }

        j = 0;
        for(int i=0;i<sLen;i++){
            while(j>0 && str.charAt(i) != pattern.charAt(j)) {
                j = next[j-1];
            }

            if (str.charAt(i) == pattern.charAt(j)) {
                j++;
            }

            if (j == pLen) {
                return i - j + 1;
            }
        }

        return -1;
    }

    static class BM{

        public int search(String str, String pattern) {
            if (str.isEmpty() || pattern.isEmpty() || pattern.length() > str.length()) return -1;
            int sLen = str.length();
            int pLen = pattern.length();

            int[] badCharTable = buildBadCharTable(pattern);
            int[] suffix = new int[pattern.length()];
            boolean[] prefix = new boolean[pattern.length()];
            buildGoodPrefix(pattern, suffix, prefix);

            int i = 0;
            while (i <= sLen - pLen) {
                int j = pLen - 1; // pattern起始比较的位置指针（从后往前）
                int k = 0; // 记录好后缀长度
                while (k < pLen && str.charAt(i + pLen - 1 - k) == pattern.charAt(j)) {
                    j--;
                    k++;
                }

                if (k == pLen) {
                    return i;
                }

                int badCharStep = j - badCharTable[str.charAt(i+j)];
                int goodSuffixStep = calGoodSuffixStep(j, pLen, suffix, prefix);
                int step  = Math.max(badCharStep, goodSuffixStep);
                i += step;
            }

            return -1;
        }

        /**
         * 使用好后缀规则计算移动的量
         * @param j       坏字符的位置
         * @param pLen    格式串的长度
         * @param suffix  各个长度好后缀的上一个位置的坐标
         * @param prefix  当前长度的好后缀是否存在最长前后缀
         * @return
         */
        private int calGoodSuffixStep(int j, int pLen, int[] suffix, boolean[] prefix) {
            // 好后缀长度
            int k = pLen - 1 - j;
            if (k == 0) {
                return 1;
            }
            /**
             * 好后缀规则计算分三种情况：
             * 第一种：
             *      如果当前好后缀在格式串中存在，那么通过好后缀表移动
             * 第二种：
             *      不满足第一种，寻找比当前好后缀短1的后缀判断是不是存在最长前后缀，
             *              如果存在，就移动pLen - 最长前后缀长度 个位置；
             *              如果不存在就再减1重复判断，直到当毒唯判断完
             * 第三种：
             *      不满足前面两种的，直接将字符串移动pLen位
             *
             * 三种情况移动的长度理论上逐渐增加，符合优先移动最小单位规则，保证不跳过任何情况的搜索；
             */
            // 第一种: 通过好后缀表移动（如果存在）
            if (suffix[k] != -1) {
                // 计算存在好后缀移动距离
                return j - suffix[k] + 1;
            }

            // 第二种: 根据最长前后缀移动移动（如果存在）
            int a = k - 1;
            while (a > 0) {
                if (prefix[a--]) {
                    return pLen - a;
                }
            }

            // 第三种：直接移动pLen位，属于最长的移动（都不存在直接移动最长距离）
            return pLen;
        }

        /**
         * 构建两个数组，因为后面要用，所以采用void返回值
         * @param pattern
         * @param suffix 存放指定长度的好后缀时，最后一个好后缀第一个字符出现的位置，没有存-1
         * @param prefix 当前长度好后缀是不是格式串的头
         */
        private static void buildGoodPrefix(String pattern, int[] suffix, boolean[] prefix) {
            Arrays.fill(suffix, -1);
            Arrays.fill(prefix, false);
            int pLen = pattern.length();

            for (int i = 0; i < pLen - 1; i++) {
                int k = 0; //记录好后缀长度
                // 从左往右判断，子串从后往前，依次判断好后缀是否存在于前面部分，如果存在记录位置（第一个字符的位置）
                /**
                 *   1。 之所以从左往右，是因为可以更新好后缀在前面部分的最右边位置，保证不会跳过有用的比较
                 *   2. 之所以从后往前，是因为比较后缀只能从后往前
                 */
                while(i - k >= 0 && pattern.charAt(i - k) == pattern.charAt(pLen - 1 - k)) {
                    k++;
                    suffix[k] = i - k + 1;
                }

                // 如果好后缀从第一个开始，如果k的长度刚好是当前位置【0，i】，表示前缀为好后缀
                /**
                 * 这里之所以需要获取好后缀是不是存在最长前后缀的，是用来判断
                 */
                if (k != 0 && i + 1 == k) {
                    prefix[k] = true;
                }
            }
        }


        /**
         * 构建坏字符表
         * @param pattern
         * @return 返回坏字符表，记录坏字符在格式串中最后出现的位置
         */
        private int[] buildBadCharTable(String pattern) {
            int len = pattern.length();
            int[] badTable = new int[256]; // ASCII字符表
            Arrays.fill(badTable, -1); // 不存在的字符为-1，因为移动长度等于 pLen - badTable[?]
            for (int i = 0; i < len; i++) {
                // 坏字符表中放的是其在格式串中最后一次出现的位置
                badTable[pattern.charAt(i)] = i;
            }

            return badTable;
        }

        private static void buildGoodSuffixTable(String pattern, int[] suffix, boolean[] prefix) {
            Arrays.fill(suffix, -1);
            Arrays.fill(prefix, false);
            int m = pattern.length();

            for (int i = 0; i < m - 1; i++) { // 遍历所有可能的前缀
                int j = i;
                int k = 0; // 公共后缀长度
                while (j >= 0 && pattern.charAt(j) == pattern.charAt(m - 1 - k)) {
                    j--;
                    k++;
                    suffix[k] = j + 1; // 记录后缀k的起始位置
                }
                if (j == -1) {
                    prefix[k] = true; // 存在长度为k的前缀与后缀匹配
                }
            }
        }

        public static void main(String[] args) {
            String pattern = "abababababa";

            int[] suffix = new int[pattern.length()];
            boolean[] prefix = new boolean[pattern.length()];
            BM.buildGoodPrefix(pattern, suffix, prefix);
            System.out.println(Arrays.toString(suffix));
            System.out.println(Arrays.toString(prefix));

            int[] suffix1 = new int[pattern.length()];
            boolean[] prefix1 = new boolean[pattern.length()];
            BM.buildGoodSuffixTable(pattern, suffix1, prefix1);
            System.out.println(Arrays.toString(suffix1));
            System.out.println(Arrays.toString(prefix1));
        }


    }


    public static void main(String[] args) {
//        String pattern = "ABABC";
//        int[] next = buildNext(pattern);
//        System.out.println(Arrays.toString(next));
//        System.out.println(Arrays.toString(buildNext_1(pattern)));
//        System.out.println(KMPsearch("fadfasadbutsad", "sad"));
//        System.out.println(SundaySearch("aaaaa", "bba"));
//        System.out.println(bruteForceSearch("mississippi", "issipi"));

//        System.out.println(sundaySearch_test("mississipi", "issipi"));
        BM bm = new BM();
//        System.out.println(bm.search("mississipi", "issipi"));

        String text = "ABAAABCDABCABCDABDE";
        String pattern = "ABCD";

        int index = bm.search(text, pattern);
        System.out.println("Pattern found at index: " + index); // 输出 4

        text = "HERE IS A SIMPLE EXAMPLE";
        pattern = "EXAMPLE";
        index = bm.search(text, pattern);
        System.out.println("Pattern found at index: " + index); // 输出 17

        text = "ABABABCABABABD";
        pattern = "ABABD";
        index = bm.search(text, pattern);
        System.out.println("Pattern found at index: " + index); // 输出 9

        text = "ABCDEFG";
        pattern = "XYZ";
        index = bm.search(text, pattern);
        System.out.println("Pattern not found: " + index); // 输出 -1
    }

}
